package demo.practice.bfs;

import demo.practice.TreeNode;

import java.util.*;

public class P107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        if (root == null)
            return new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        Stack<List<Integer>> stack = new Stack<>();

        queue.add(root);

        while (!queue.isEmpty()) {
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while (len > 0) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null)
                    queue.add(poll.left);

                if (poll.right != null)
                    queue.add(poll.right);
                len--;
            }
            stack.add(list);
        }
        List<List<Integer>> res= new ArrayList<>();
        while (!stack.isEmpty()){
            res.add(stack.pop());
        }

        return res;
    }
}
